/** *****************************************************************************
 * Copyright 2011 See AUTHORS file.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ***************************************************************************** */
package com.kaka.util;

import java.io.Serializable;
import java.util.NoSuchElementException;

/**
 * An unordered set that uses int keys. This implementation uses cuckoo hashing
 * using 3 hashes, random walking, and a small stash for problematic keys. No
 * allocation is done except when growing the table size. <br>
 * <br>
 * This set performs very fast contains and remove (typically O(1), worst case
 * O(log(n))). Add may be a bit slower, depending on hash collisions. Load
 * factors greater than 0.91 greatly increase the chances the set will have to
 * rehash to the next higher POT size.
 *
 * @author Nathan Sweet
 */
public class IntSet implements Serializable {

    private static final int PRIME1 = 0xbe1f14b1;
    private static final int PRIME2 = 0xb4b82e39;
    private static final int PRIME3 = 0xced1c241;
    private static final int EMPTY = 0;

    int size;

    int[] keyTable;
    int capacity, stashSize;
    boolean hasZeroValue;

    private float loadFactor;
    private int hashShift, mask, threshold;
    private int stashCapacity;
    private int pushIterations;

    private IntSetIterator iterator1, iterator2;

    /**
     * Creates a new set with an initial capacity of 51 and a load factor of
     * 0.8.
     */
    public IntSet() {
        this(51, 0.8f);
    }

    /**
     * Creates a new set with a load factor of 0.8.
     *
     * @param initialCapacity If not a power of two, it is increased to the next
     * nearest power of two.
     */
    public IntSet(int initialCapacity) {
        this(initialCapacity, 0.8f);
    }

    /**
     * Creates a new set with the specified initial capacity and load factor.
     * This set will hold initialCapacity items before growing the backing
     * table.
     *
     * @param initialCapacity If not a power of two, it is increased to the next
     * nearest power of two.
     */
    public IntSet(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity);
        }
        initialCapacity = MathUtils.nextPowerOfTwo((int) Math.ceil(initialCapacity / loadFactor));
        if (initialCapacity > 1 << 30) {
            throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity);
        }
        capacity = initialCapacity;

        if (loadFactor <= 0) {
            throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor);
        }
        this.loadFactor = loadFactor;

        threshold = (int) (capacity * loadFactor);
        mask = capacity - 1;
        hashShift = 31 - Integer.numberOfTrailingZeros(capacity);
        stashCapacity = Math.max(3, (int) Math.ceil(Math.log(capacity)) * 2);
        pushIterations = Math.max(Math.min(capacity, 8), (int) Math.sqrt(capacity) / 8);

        keyTable = new int[capacity + stashCapacity];
    }

    /**
     * Creates a new set identical to the specified set.
     */
    public IntSet(IntSet set) {
        this((int) Math.floor(set.capacity * set.loadFactor), set.loadFactor);
        stashSize = set.stashSize;
        System.arraycopy(set.keyTable, 0, keyTable, 0, set.keyTable.length);
        size = set.size;
        hasZeroValue = set.hasZeroValue;
    }

    /**
     * Returns true if the key was not already in the set.
     */
    public boolean add(int key) {
        if (key == 0) {
            if (hasZeroValue) {
                return false;
            }
            hasZeroValue = true;
            size++;
            return true;
        }

        int[] keyTable = this.keyTable;

        // Check for existing keys.
        int index1 = key & mask;
        int key1 = keyTable[index1];
        if (key1 == key) {
            return false;
        }

        int index2 = hash2(key);
        int key2 = keyTable[index2];
        if (key2 == key) {
            return false;
        }

        int index3 = hash3(key);
        int key3 = keyTable[index3];
        if (key3 == key) {
            return false;
        }

        // Find key in the stash.
        for (int i = capacity, n = i + stashSize; i < n; i++) {
            if (keyTable[i] == key) {
                return false;
            }
        }

        // Check for empty buckets.
        if (key1 == EMPTY) {
            keyTable[index1] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return true;
        }

        if (key2 == EMPTY) {
            keyTable[index2] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return true;
        }

        if (key3 == EMPTY) {
            keyTable[index3] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return true;
        }

        push(key, index1, key1, index2, key2, index3, key3);
        return true;
    }

    public void addAll(IntArray array) {
        addAll(array, 0, array.size);
    }

    public void addAll(IntArray array, int offset, int length) {
        if (offset + length > array.size) {
            throw new IllegalArgumentException("offset + length must be <= size: " + offset + " + " + length + " <= " + array.size);
        }
        addAll(array.items, offset, length);
    }

    public void addAll(int... array) {
        addAll(array, 0, array.length);
    }

    public void addAll(int[] array, int offset, int length) {
        ensureCapacity(length);
        for (int i = offset, n = i + length; i < n; i++) {
            add(array[i]);
        }
    }

    public void addAll(IntSet set) {
        ensureCapacity(set.size);
        IntSetIterator iterator = set.iterator();
        while (iterator.hasNext) {
            add(iterator.next());
        }
    }

    /**
     * Skips checks for existing keys.
     */
    private void addResize(int key) {
        if (key == 0) {
            hasZeroValue = true;
            return;
        }

        // Check for empty buckets.
        int index1 = key & mask;
        int key1 = keyTable[index1];
        if (key1 == EMPTY) {
            keyTable[index1] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return;
        }

        int index2 = hash2(key);
        int key2 = keyTable[index2];
        if (key2 == EMPTY) {
            keyTable[index2] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return;
        }

        int index3 = hash3(key);
        int key3 = keyTable[index3];
        if (key3 == EMPTY) {
            keyTable[index3] = key;
            if (size++ >= threshold) {
                resize(capacity << 1);
            }
            return;
        }

        push(key, index1, key1, index2, key2, index3, key3);
    }

    private void push(int insertKey, int index1, int key1, int index2, int key2, int index3, int key3) {
        int[] keyTable = this.keyTable;

        int mask = this.mask;

        // Push keys until an empty bucket is found.
        int evictedKey;
        int i = 0, pushIterations = this.pushIterations;
        do {
            // Replace the key and value for one of the hashes.
            switch (MathUtils.random(2)) {
                case 0:
                    evictedKey = key1;
                    keyTable[index1] = insertKey;
                    break;
                case 1:
                    evictedKey = key2;
                    keyTable[index2] = insertKey;
                    break;
                default:
                    evictedKey = key3;
                    keyTable[index3] = insertKey;
                    break;
            }

            // If the evicted key hashes to an empty bucket, put it there and stop.
            index1 = evictedKey & mask;
            key1 = keyTable[index1];
            if (key1 == EMPTY) {
                keyTable[index1] = evictedKey;
                if (size++ >= threshold) {
                    resize(capacity << 1);
                }
                return;
            }

            index2 = hash2(evictedKey);
            key2 = keyTable[index2];
            if (key2 == EMPTY) {
                keyTable[index2] = evictedKey;
                if (size++ >= threshold) {
                    resize(capacity << 1);
                }
                return;
            }

            index3 = hash3(evictedKey);
            key3 = keyTable[index3];
            if (key3 == EMPTY) {
                keyTable[index3] = evictedKey;
                if (size++ >= threshold) {
                    resize(capacity << 1);
                }
                return;
            }

            if (++i == pushIterations) {
                break;
            }

            insertKey = evictedKey;
        } while (true);

        addStash(evictedKey);
    }

    private void addStash(int key) {
        if (stashSize == stashCapacity) {
            // Too many pushes occurred and the stash is full, increase the table size.
            resize(capacity << 1);
            add(key);
            return;
        }
        // Store key in the stash.
        int index = capacity + stashSize;
        keyTable[index] = key;
        stashSize++;
        size++;
    }

    /**
     * Returns true if the key was removed.
     */
    public boolean remove(int key) {
        if (key == 0) {
            if (!hasZeroValue) {
                return false;
            }
            hasZeroValue = false;
            size--;
            return true;
        }

        int index = key & mask;
        if (keyTable[index] == key) {
            keyTable[index] = EMPTY;
            size--;
            return true;
        }

        index = hash2(key);
        if (keyTable[index] == key) {
            keyTable[index] = EMPTY;
            size--;
            return true;
        }

        index = hash3(key);
        if (keyTable[index] == key) {
            keyTable[index] = EMPTY;
            size--;
            return true;
        }

        return removeStash(key);
    }

    boolean removeStash(int key) {
        int[] keyTable = this.keyTable;
        for (int i = capacity, n = i + stashSize; i < n; i++) {
            if (keyTable[i] == key) {
                removeStashIndex(i);
                size--;
                return true;
            }
        }
        return false;
    }

    void removeStashIndex(int index) {
        // If the removed location was not last, move the last tuple to the removed location.
        stashSize--;
        int lastIndex = capacity + stashSize;
        if (index < lastIndex) {
            keyTable[index] = keyTable[lastIndex];
        }
    }

    /**
     * Reduces the size of the backing arrays to be the specified capacity or
     * less. If the capacity is already less, nothing is done. If the set
     * contains more items than the specified capacity, the next highest power
     * of two capacity is used instead.
     */
    public void shrink(int maximumCapacity) {
        if (maximumCapacity < 0) {
            throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity);
        }
        if (size > maximumCapacity) {
            maximumCapacity = size;
        }
        if (capacity <= maximumCapacity) {
            return;
        }
        maximumCapacity = MathUtils.nextPowerOfTwo(maximumCapacity);
        resize(maximumCapacity);
    }

    /**
     * Clears the set and reduces the size of the backing arrays to be the
     * specified capacity if they are larger.
     */
    public void clear(int maximumCapacity) {
        if (capacity <= maximumCapacity) {
            clear();
            return;
        }
        hasZeroValue = false;
        size = 0;
        resize(maximumCapacity);
    }

    public void clear() {
        if (size == 0) {
            return;
        }
        int[] keyTable = this.keyTable;
        for (int i = capacity + stashSize; i-- > 0;) {
            keyTable[i] = EMPTY;
        }
        size = 0;
        stashSize = 0;
        hasZeroValue = false;
    }

    public boolean contains(int key) {
        if (key == 0) {
            return hasZeroValue;
        }
        int index = key & mask;
        if (keyTable[index] != key) {
            index = hash2(key);
            if (keyTable[index] != key) {
                index = hash3(key);
                if (keyTable[index] != key) {
                    return containsKeyStash(key);
                }
            }
        }
        return true;
    }

    private boolean containsKeyStash(int key) {
        int[] keyTable = this.keyTable;
        for (int i = capacity, n = i + stashSize; i < n; i++) {
            if (keyTable[i] == key) {
                return true;
            }
        }
        return false;
    }

    public int first() {
        if (hasZeroValue) {
            return 0;
        }
        int[] keyTable = this.keyTable;
        for (int i = 0, n = capacity + stashSize; i < n; i++) {
            if (keyTable[i] != EMPTY) {
                return keyTable[i];
            }
        }
        throw new IllegalStateException("IntSet is empty.");
    }

    /**
     * Increases the size of the backing array to accommodate the specified
     * number of additional items. Useful before adding many items to avoid
     * multiple backing array resizes.
     */
    public void ensureCapacity(int additionalCapacity) {
        int sizeNeeded = size + additionalCapacity;
        if (sizeNeeded >= threshold) {
            resize(MathUtils.nextPowerOfTwo((int) Math.ceil(sizeNeeded / loadFactor)));
        }
    }

    private void resize(int newSize) {
        int oldEndIndex = capacity + stashSize;

        capacity = newSize;
        threshold = (int) (newSize * loadFactor);
        mask = newSize - 1;
        hashShift = 31 - Integer.numberOfTrailingZeros(newSize);
        stashCapacity = Math.max(3, (int) Math.ceil(Math.log(newSize)) * 2);
        pushIterations = Math.max(Math.min(newSize, 8), (int) Math.sqrt(newSize) / 8);

        int[] oldKeyTable = keyTable;

        keyTable = new int[newSize + stashCapacity];

        int oldSize = size;
        size = hasZeroValue ? 1 : 0;
        stashSize = 0;
        if (oldSize > 0) {
            for (int i = 0; i < oldEndIndex; i++) {
                int key = oldKeyTable[i];
                if (key != EMPTY) {
                    addResize(key);
                }
            }
        }
    }

    private int hash2(int h) {
        h *= PRIME2;
        return (h ^ h >>> hashShift) & mask;
    }

    private int hash3(int h) {
        h *= PRIME3;
        return (h ^ h >>> hashShift) & mask;
    }

    public int hashCode() {
        int h = 0;
        for (int i = 0, n = capacity + stashSize; i < n; i++) {
            if (keyTable[i] != EMPTY) {
                h += keyTable[i];
            }
        }
        return h;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof IntSet)) {
            return false;
        }
        IntSet other = (IntSet) obj;
        if (other.size != size) {
            return false;
        }
        if (other.hasZeroValue != hasZeroValue) {
            return false;
        }
        for (int i = 0, n = capacity + stashSize; i < n; i++) {
            if (keyTable[i] != EMPTY && !other.contains(keyTable[i])) {
                return false;
            }
        }
        return true;
    }

    public String toString() {
        if (size == 0) {
            return "[]";
        }
        StringBuilder buffer = new StringBuilder(32);
        buffer.append('[');
        int[] keyTable = this.keyTable;
        int i = keyTable.length;
        if (hasZeroValue) {
            buffer.append("0");
        } else {
            while (i-- > 0) {
                int key = keyTable[i];
                if (key == EMPTY) {
                    continue;
                }
                buffer.append(key);
                break;
            }
        }
        while (i-- > 0) {
            int key = keyTable[i];
            if (key == EMPTY) {
                continue;
            }
            buffer.append(", ");
            buffer.append(key);
        }
        buffer.append(']');
        return buffer.toString();
    }

    /**
     * Returns an iterator for the keys in the set. Remove is supported. Note
     * that the same iterator instance is returned each time this method is
     * called. Use the {@link IntSetIterator} constructor for nested or
     * multithreaded iteration.
     */
    public IntSetIterator iterator() {
        if (iterator1 == null) {
            iterator1 = new IntSetIterator(this);
            iterator2 = new IntSetIterator(this);
        }
        if (!iterator1.valid) {
            iterator1.reset();
            iterator1.valid = true;
            iterator2.valid = false;
            return iterator1;
        }
        iterator2.reset();
        iterator2.valid = true;
        iterator1.valid = false;
        return iterator2;
    }

    static public IntSet with(int... array) {
        IntSet set = new IntSet();
        set.addAll(array);
        return set;
    }

    public int size() {
        return size;
    }

    static public class IntSetIterator {

        static final int INDEX_ILLEGAL = -2;
        static final int INDEX_ZERO = -1;

        public boolean hasNext;

        final IntSet set;
        int nextIndex, currentIndex;
        boolean valid = true;

        public IntSetIterator(IntSet set) {
            this.set = set;
            reset();
        }

        public void reset() {
            currentIndex = INDEX_ILLEGAL;
            nextIndex = INDEX_ZERO;
            if (set.hasZeroValue) {
                hasNext = true;
            } else {
                findNextIndex();
            }
        }

        void findNextIndex() {
            hasNext = false;
            int[] keyTable = set.keyTable;
            for (int n = set.capacity + set.stashSize; ++nextIndex < n;) {
                if (keyTable[nextIndex] != EMPTY) {
                    hasNext = true;
                    break;
                }
            }
        }

        public void remove() {
            if (currentIndex == INDEX_ZERO && set.hasZeroValue) {
                set.hasZeroValue = false;
            } else if (currentIndex < 0) {
                throw new IllegalStateException("next must be called before remove.");
            } else if (currentIndex >= set.capacity) {
                set.removeStashIndex(currentIndex);
                nextIndex = currentIndex - 1;
                findNextIndex();
            } else {
                set.keyTable[currentIndex] = EMPTY;
            }
            currentIndex = INDEX_ILLEGAL;
            set.size--;
        }

        public int next() {
            if (!hasNext) {
                throw new NoSuchElementException();
            }
            if (!valid) {
                throw new RuntimeException("#iterator() cannot be used nested.");
            }
            int key = nextIndex == INDEX_ZERO ? 0 : set.keyTable[nextIndex];
            currentIndex = nextIndex;
            findNextIndex();
            return key;
        }

        /**
         * Returns a new array containing the remaining keys.
         */
        public IntArray toArray() {
            IntArray array = new IntArray(true, set.size);
            while (hasNext) {
                array.add(next());
            }
            return array;
        }
    }
}
